package tp2;

import java.util.LinkedList;
import java.util.List;

import tp2.Pair;
public class PatriciaTrie {

	private TrieNode _raiz;
    private int _cantPalabras;
    
    private Estadistica es;
    
//Implementacion --------------------------------------------------------------
 public PatriciaTrie(Estadistica esEnt){
	 es = esEnt;
	 _raiz = new TrieNode(es);
	 _raiz._significado = null;
	 _cantPalabras = 0;
 }
 
 public int cantPalabras(){
	 return _cantPalabras;
	 
 }
/*
public PatriciaTrie(PatriciaTrie d) {
  this.asignar(d);
}
*/
public void definir(StringC clave,String significado){
	StringC aux = clave;

  _definir(aux, significado, _raiz,0);
  _cantPalabras++;
}

public String obtener(StringC clave){
	StringC aux = clave;
  return _obtener(aux, _raiz);
}


public boolean estaDefinido(StringC clave){
	StringC aux = clave;
  return _estaDefinido(aux, _raiz);
}

public void borrar(StringC clave) {
	StringC aux = clave;
  _borrar(aux, _raiz);
  _cantPalabras--;
}
/*
public PatriciaTrie asignar(PatriciaTrie d){
  if(this != d){
	_raiz = null;
	_raiz.copiar(d._raiz);
  }
  return this;
}
*/
//Funciones Auxiliares --------------------------------------------------------

private void _definir(StringC clave, String significado, TrieNode tn, int cantP) {
	StringC str = new StringC("piano",es);
	if(clave.comparar(0, str, 0, 5)){
		str.length();
	}
	if(clave.comparar(0, str, 0, 5)){
		str.length();
	}
	es.op++;
	Pair<Boolean,Integer> esHijo = tn.esHijo(clave);	//O(|hasta|)
	int hasta = esHijo.scd.intValue();

	if(!esHijo.fst || (tn._clave!=null && cantP<tn._clave.length())){						
		if(tn._clave!=null && tn._clave.length() > (cantP)){			// si tengo que partir un nodo
								
			TrieNode newT = new TrieNode(es);
			newT._hijos.addAll(tn._hijos);
			for(TrieNode h:tn._hijos)
				h._padre=newT;
			tn._hijos.clear();
			tn._hijos.add(newT);
			newT._padre = tn;
			newT._significado=tn._significado;
			tn._significado = null;
			StringC sAux= new StringC(tn._clave,es);
			newT._clave = new StringC(tn._clave.substring(cantP),es);
			tn._clave = new StringC(sAux.substring(0, cantP),es);
			
			clave.resetear();														//hasta aca dividi el nodo
			_definir(clave,significado,this._raiz,0); 		// ahora agrego la palabra nueva
																	
		}
		else{											// si inserto un nodo hoja
			TrieNode newT = new TrieNode(es);
			newT._significado = significado;
			newT._clave = clave;
			newT._padre = tn;
			tn._hijos.add(newT);
			return;
		}
	}
	else{									// si el nodo tiene prefijo
		int indice = tn.indiceDe(clave,hasta);
	clave = clave.substring(hasta); //O(|clave|-hasta) //esto cambiar si o si

		_definir(clave,significado,tn._hijos.get(indice),hasta); //O(|clave|)

	}
}	
	
/*	
private static Pair<Boolean,Integer> esPrefijo(String s1,String s2){
	  if(s1==null||s2==null) return new Pair<Boolean,Integer>(new Boolean(true),new Integer(0));
	  int i = 0;
	  if(s1.substring(0, 1).equals(s2.substring(0, 1))){
		  for( i = 1;i<=s2.length() && s1.startsWith(s2.substring(0, i));i++);
		  return new Pair<Boolean,Integer>(new Boolean(true),new Integer(i-1));
		  }
		  
	return new Pair<Boolean,Integer>(new Boolean(false),new Integer(0));
}
*/
 private boolean _compactar(TrieNode tPadre){
	 if((tPadre._significado==null)&&tPadre._hijos.size()==1&& tPadre._clave!=null){
		 tPadre._clave = new StringC(tPadre._clave.concatAstring(tPadre._hijos.get(0)._clave),es);
		 tPadre._significado = tPadre._hijos.get(0)._significado;
		 List<TrieNode> hijosAux= new LinkedList(tPadre._hijos.get(0)._hijos);
		 for(TrieNode h:hijosAux)
			 	h._padre=tPadre;
		 tPadre._hijos.clear();
		 tPadre._hijos = hijosAux;
		 
		 return true;
	 }
	 return false;
 }
	
private void _borrar(StringC clave, TrieNode tn) {
	es.op++;
	if(clave.vacia() && tn!=_raiz){						// si llegue a la hoja
		tn._significado=null;
		if(tn._hijos.size()==0){							
			tn._padre._hijos.remove(tn);
			if(this._cantPalabras>1)
			_compactar(tn._padre);
		}
		return;
	}
	Pair<Boolean,Integer> esHijo = tn.esHijo(clave);
	int hasta = (int)esHijo.scd;
	if(esHijo.fst){
		int indice = tn.indiceDe(clave,hasta);
		StringC claveAux = clave.substring(hasta);
		_borrar(claveAux,tn._hijos.get(indice));
	}
}
	

private boolean _estaDefinido(StringC clave, TrieNode tn) {
	es.op++;
  if(clave == null  || clave.length() == 0 ){
	    return (tn._significado != null);

  } else {
	 
		Pair<Boolean,Integer> esHijo = tn.esHijo(clave);
		if(!esHijo.fst)return false;
		int indice = tn.indiceDe(clave,(int)esHijo.scd);
		StringC newS = clave.substring((int)esHijo.scd);
      return _estaDefinido(newS, tn._hijos.get(indice));
    }
}

public TrieNode raiz(){
	return this._raiz;
}

private String _obtener(StringC clave, TrieNode tn) {
	es.op++;
  if(clave.length() == 0){
    return tn._significado;
  } else {
	  	Pair<Boolean,Integer> esHijo = tn.esHijo(clave);
	  	int indice = tn.indiceDe(clave,(int)esHijo.scd);
		StringC newS = clave.substring((int)esHijo.scd);
	    //String newS;
	    //if (clave.length()>1) newS = clave.substring(1); else newS=null;
   return  _obtener(newS, tn._hijos.get(indice));
  }

}
/*
public void mostrar(){
	_mostrar(_raiz);
}

private static void _mostrar(TrieNode t){
	
	for(TrieNode tn : t._hijos){
		System.out.println(tn._clave);
	}
}
*/








}
